/**
 * https://leetcode.cn/submissions/detail/559911695/
 * 76. 最小覆盖子串
 * Hard 黄伟杰 2024.8.30
 * 滑动窗口
 */

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    string minWindow(string s, string t)
    {
        unordered_map<char, int> need, window;
        for (char ch : t)
            need[ch]++;
        int left = 0, right = 0, start = 0, len = 1e8 + 5, cnt = 0;
        while (right < s.size())
        {
            char ch = s[right];
            right++;
            if (need.count(ch))
            {
                window[ch]++;
                if (window[ch] == need[ch])
                    cnt++;
            }
            while (cnt == need.size())
            {
                if (right - left < len)
                {
                    start = left;
                    len = right - left;
                }
                char c = s[left];
                left++;
                if (need.count(c))
                {
                    if (window[c] == need[c])
                        cnt--;
                    window[c]--;
                }
            }
        }
        return len == 1e8 + 5 ? "" : s.substr(start, len);
    }
};